#pragma once
#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

namespace dzp
{
    template<class K>
    struct SkipListNode
    {
        K key;
        vector<SkipListNode*> next;

        SkipListNode(const K& _key, size_t m = 1)
            :key(_key)
            , next(m, nullptr)
        {}
    };
    // Key  p是其他层数的概念  N是多少层
    template<class K, class P, size_t M = 32>
    class skiplist
    {
        typedef SkipListNode<K> Node;
    public:
        skiplist(const P& _p)
            :p(_p)
        {
            srand(time(0));
            root = new Node(-1, 1);
        }

        bool search(const K& key)
        {
            int end = root->next.size() - 1;
            Node* cur = root;
            while (end >= 0)
            {
                if (cur -> next[end] == nullptr || key < cur->next[end]->key)
                {
                    --end;
                }
                else if (cur->next[end] && key > cur->next[end]->key)
                {
                    cur = cur->next[end];
                }
                else
                {
                    return true;
                }
            }
            return false;
        }

        //查找key的位置
        vector<Node*> FindPrevNode(const K& key)
        {
            Node* cur = root;
            int level = root->next.size() - 1;
            vector<Node*> prev(level + 1, root);//保存新增的最高层的前一个

            while (level >= 0)
            {
                if (cur->next[level] && key > cur->next[level]->key)
                {
                    //向右走
                    cur = cur->next[level];
                }else if(cur->next[level] == nullptr || key <= cur->next[level]->key)//
                {
                    //向下走 并保存新增需要连接的前一个节点
                    prev[level] = cur;
                    level--;
                }
            }
            return prev;
        }

        //随机层
        size_t randomlevel()
        {
           size_t level = 1;
            //[0 ,RAND_MAX] 只要小于RAND_MAX*p 就是 1-p的几率
            while (rand() < RAND_MAX * p && level < M)
            {
                ++level;
            }
            return level;
        }
        void add(const K& key)
        {
            vector<Node*> prevV = FindPrevNode(key);

            //获得随机层数
            size_t n = randomlevel();
            Node* cur = new Node(key, n);

            //n高于root的层数是需要更新
            if ( n > root->next.size())
            {
                root->next.resize(n);
                prevV.resize(n, root);
            }

            //添加新节点
            for (int i = 0; i < n; ++i)
            {
                cur->next[i] = prevV[i]->next[i];
                prevV[i]->next[i] = cur;

            }
        }

        bool erase(const K& key)
        {
            vector<Node*> pervV = FindPrevNode(key);
            if (pervV[0]->next[0] == nullptr || pervV[0]->next[0]->key != key)
                return false;

            Node* cur = pervV[0]->next[0];
            for (int i = 0; i < cur->next.size(); ++i)
            {
                pervV[i]->next[i] = cur->next[i];
            }
            delete cur;

            //把root的最高层没有连接的都去掉
            int i = root->next.size() - 1;
            while (i >= 0)
            {
                if (root->next[i] == nullptr)
                    --i;
                else
                    break;
            }
            root->next.resize(i + 1);
            return true;

        }

        void Print()
        {
            /*int level = _head->_nextV.size();
            for (int i = level - 1; i >= 0; --i)
            {
                Node* cur = _head;
                while (cur)
                {
                    printf("%d->", cur->_val);
                    cur = cur->_nextV[i];
                }
                printf("\n");
            }*/

            Node* cur =root;
            while (cur)
            {
                printf("%2d\n", cur->key);
                // 打印每个每个cur节点
                for (auto e : cur->next)
                {
                    printf("%2s", "↓");
                }
                printf("\n");

                cur = cur->next[0];
            }
        }
    private:
        Node* root = nullptr;
        P p;

    };
}